public class MaxProfit2 {

    public static void main(String[] args) {
        int[] nums = {2, 1, 2, 1, 0, 0, 1};
        System.out.println(new MaxProfit2().maxProfit(nums));
    }

    public int maxProfit1(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        int min = prices[0];
        int ans = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = prices[i] - min;
            int index = i - 1 < 0 ? 0 : i - 1;
            int temp = prices[index];
            for (int j = i - 3; j >= 0; j--) {
                dp[i] = Math.max(dp[i], prices[i] - temp + dp[j]);
                temp = Math.min(temp, prices[--index]);
            }
            ans = Math.max(ans, dp[i]);
            min = Math.min(min, prices[i]);
        }
        return ans;
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0]; //有股票
        dp[0][1] = 0; //今天卖出
        dp[0][2] = 0; //手上没股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][0]);
            dp[i][1] = prices[i] + dp[i - 1][0];
            dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
        }
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }
}
